package _2_leetcode_21_40._22括号生成;

import java.util.ArrayList;
import java.util.List;

/**
 * @author mazexal
 * @version
 * @Date 22:25 2021/1/10
 * @Description: 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * https://leetcode-cn.com/problems/generate-parentheses/
 */
class Solution {

    public static void main(String[] args) {
        List<String> list = generateParenthesis(3);
        for (String item : list) {
            System.out.println(item);
        }
    }

    /**
     * @author mazexal
     * @version
     * @Date 22:33 2021/1/10
     * @Description: 这里用了回溯法
     * @Return
     * @Exception
     */
    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public static void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

